home *** CD-ROM | disk | FTP | other *** search
/ Aminet 31 / Aminet 31 (1999)(Schatztruhe)[!][Jun 1999].iso / Aminet / dev / c / cflow.lha / cflow-2.0 / prcg.c < prev    next >
C/C++ Source or Header  |  1999-02-20  |  14KB  |  505 lines
  1.  
  2. /* This file contains code for building and printing a directed cyclic
  3.  * graph as part of the cflow program. */
  4.  
  5. /* Author: M.M. Taylor, DCIEM, Toronto, Canada.
  6.  * 22/Jan/81, Alexis Kwan (HCR at DCIEM).
  7.  * 12-Jun-84, Kevin Szabo
  8.  * 8/8/84, Tony Hansen, AT&T-IS, pegasus!hansen. 
  9.  * 
  10.  * This file is contributed to the public domain by Andrew Moore of
  11.  * Talke Studio */
  12.  
  13. #include <stdio.h>
  14. #include <stdlib.h>
  15. #include <ctype.h>
  16. #include <string.h>
  17.  
  18. #include "prcg.prototypes.h"
  19. #ifndef PATH_MAX
  20. #define PATH_MAX 1024        /* max pathname length */
  21. #endif
  22. #ifndef NAME_MAX
  23. #define NAME_MAX 32
  24. #endif
  25.  
  26. #define BUF_MAX (NAME_MAX * 2 + PATH_MAX + 20)    /* max line buffer length */
  27. #define DEPTH_MAX 200        /* max path length */
  28. #define TABSIZE 8        /* tab size */
  29. #define MARGIN 20        /* right margin of paper */
  30. #define PAPERWIDTH (14*TABSIZE + MARGIN)    /* tabbing limits */
  31.  
  32. #ifndef __P
  33. #ifndef __STDC__
  34. #define __P(proto) ()
  35. #else
  36. #define __P(proto) proto
  37. #endif
  38. #endif
  39.  
  40. /* name list node */
  41. struct name_node {
  42.     struct name_node *next;    /* next name list node */
  43.     struct imm_node *imm_list;    /* node's immediate list */
  44.     long name_visited;    /* set if node previously visited */
  45.     int is_arc_head;    /* set if node is an arc head */
  46.     char *imm_name;        /* name of first imm_list node */
  47.     char *imm_ref;        /* reference to first imm_list node */
  48. };
  49.  
  50. /* immediate list node */
  51. struct imm_node {
  52.     struct imm_node *next;    /* next immediate list node */
  53.     struct name_node *name_node_p;    /* node's name node pointer */
  54. };
  55.  
  56.  
  57. /* The name list (nlist) contains names (e.g., function/variable) in
  58.  * lexicographical order.  Each name node has its own  list (imm_list) of
  59.  * immediates (e.g., callers/callees).  The immediate nodes do not
  60.  * themselves have names;  instead, each node has a pointer to its name
  61.  * (node) in the name list.  The nodes and pointers form the vertices and
  62.  * edges, respectively, of a directed cyclic graph (DCG).
  63.  * 
  64.  * The prcg program builds a DCG by inserting names pairs from the input
  65.  * as arcs into the graph.  Printing the DCG is done by a preorder
  66.  * traversal from a root name node.   Paths are defined by the immediate
  67.  * list of the root name node, and, recursively, by the immediate lists
  68.  * of its immediates. */
  69. /* where is this initialized? */
  70.  
  71. static struct name_node *nlist;
  72. static char *dashes;        /* separators for deep nestings */
  73.  
  74. /* The following options are available :
  75.  * 
  76.  * -a       print a separate graph for each name (default: no)
  77.  * -d nn    print graphs to at most depth `nn' (default: 200)
  78.  * -r root  print graph only for `root' (default: each root name)
  79.  * -x       print each sub-graph in full (default: no)
  80.  * -w nn    print graph to fit in `nn' columns (default: 132 columns) */
  81.  
  82. /* option flags */
  83. static int graph_all = 0;    /* print a graph for each name */
  84. static int maxdepth = DEPTH_MAX;    /* print to at most depth `maxdepth' */
  85. static int expand_all = 0;    /* print each sub-graph in full */
  86. static int ntabs = ((PAPERWIDTH - MARGIN) / TABSIZE);    /* how wide to go */
  87. static int select_roots = 0;    /* print graph for selected names */
  88.  
  89. static char *arglist = "ad:r:ixw:";    /* valid options */
  90.  
  91. static char *progname;        /* argv[0] */
  92.  
  93. extern char *optarg;
  94. extern int optind;
  95.  
  96. static void usage(void)
  97. {
  98.  
  99.     fprintf(stderr, "Usage: %s [-ax ] [-d depth] [-r root]\n", progname);
  100.     exit(1);
  101. }
  102.  
  103. main(int argc, char **argv)
  104. {
  105.  
  106.     int c, i;
  107.     int width = PAPERWIDTH;
  108.  
  109.     progname = argv[0];
  110.  
  111.     while ((c = getopt(argc, argv, arglist)) != EOF)
  112.         switch (c) {
  113.             case 'a':
  114.                 graph_all = 1;
  115.                 break;
  116.             case 'd':
  117.                 if ((maxdepth = atoi(optarg)) > DEPTH_MAX)
  118.                     maxdepth = DEPTH_MAX;
  119.                 break;
  120.             case 'i':
  121.                 expand_all = 1;
  122.                 graph_all = 1;
  123.                 maxdepth = 2;
  124.                 break;
  125.             case 'r':
  126.                 select_roots = 1;
  127.                 break;
  128.             case 'w':
  129.                 if ((width = atoi(optarg)) <= 0)
  130.                     width = PAPERWIDTH;
  131.                 break;
  132.             case 'x':
  133.                 expand_all = 1;
  134.                 break;
  135.             case '?':
  136.             default:
  137.                 usage();
  138.         }
  139.     ntabs = (width - MARGIN) / TABSIZE;
  140.  
  141.     build_dcg();
  142.     print_dcg(argc, argv);
  143.     exit(0);
  144. }
  145.  
  146. /* Name pairs in the input are expected in blocks of the form:
  147.  * 
  148.  * name1a --> name2aa
  149.  * name1a --> name2ab
  150.  * name1a --> name2ac
  151.  * .
  152.  * .
  153.  * .
  154.  * name1b --> name2ba
  155.  * name1b --> name2bb
  156.  * name1b --> name2bc
  157.  * .
  158.  * .
  159.  * .
  160.  * 
  161.  * For a distinct name1, only the first block of name pairs is valid.  A
  162.  * graph can be inverted by reversing the relation between name pairs,
  163.  * i.e., by putting name2 first:
  164.  * 
  165.  * name2 --> name1
  166.  * 
  167.  * Unless a block contains only a single name pair, then an initial
  168.  * name1-name1 pair is effectively ignored.  A name1-name1 pair after the
  169.  * first represents a cycle - i.e., a node which points to itself.  A
  170.  * block consisting of a single name1-name1 pair represents a non-cyclic,
  171.  * possibly disconnected, node. */
  172.  
  173. static struct imm_node *imm_tail;    /* immediate list tail */
  174.  
  175. /* Get name pairs from the input, and  insert them as arcs to the DCG: an
  176.  * arc tail is the head of a linearly linked list (the immediate list) of
  177.  * arc heads to which it is connected (logically).  */
  178. static void build_dcg(void)
  179. {
  180.     char arc_tail[BUF_MAX];    /* line buffer and arc tail name */
  181.     char *arc_head;        /* arc head name */
  182.     char *arc_ref;        /* arc reference */
  183.     register int connected;
  184.  
  185.     while ((connected = get_arc(arc_tail, &arc_head, &arc_ref)) != -1)
  186.         if (!connected)
  187.             imm_tail = create_arc_node(arc_tail, arc_ref);
  188.         else if (connected && imm_tail)
  189.             imm_tail = link_arc_node(arc_head, imm_tail);
  190.         else
  191.             fprintf(stderr, "%s: cannot redefine: %s\n", progname, arc_tail);
  192. }
  193.  
  194.  
  195. char tail_name[NAME_MAX] = "";    /* previous arc tail name */
  196.  
  197. /* Read from stdin a name pair and a reference in the form
  198.  * `name1<tab>name2<tab>reference<newline>.' Return 1 if the tail of arc
  199.  * name1 --> name2 (i.e., name1) is the tail the previous arc,
  200.  * otherwise 0. */
  201. get_arc(char *buf, char **ip, char **rp)
  202. {
  203.  
  204.     /* line read and data format okay */
  205.     if (fgets(buf, BUF_MAX, stdin) != NULL
  206.         && (*ip = strchr(buf, '\t')) != NULL
  207.         && (*rp = strchr(*ip + 1, '\t')) != NULL) {
  208.         /* null-terminate name1 and name2 substrings */
  209.         *(*rp)++ = *(*ip)++ = '\0';
  210.  
  211.         /* arc tail not previous tail */
  212.         if (strcmp(buf, tail_name)) {
  213.             /* update arc tail name */
  214.             strcpy(tail_name, buf);
  215.  
  216.             /* name pair is an arc (as opposed to a node) */
  217.             if (strcmp(buf, *ip)) {
  218.                 /* create an arc tail node */
  219.                 imm_tail = create_arc_node(buf, *rp);
  220.  
  221.                 /* arc */
  222.                 return 1;
  223.             }
  224.             /* node */
  225.             return 0;
  226.         }
  227.         /* arc */
  228.         return 1;
  229.     }
  230.     /* eof */
  231.     return -1;
  232. }
  233.  
  234.  
  235. /* Given a name (s), if it is not already on the name list, create a node
  236.  * for it there.  Otherwise, retrieve the name list node.  Create an arc
  237.  * tail (i.e., imm_list) node and link it to the new/retrieved name
  238.  * node (via the name node's imm_list pointer).  Return a pointer to the
  239.  * arc tail node. */
  240. struct imm_node *
  241.  create_arc_node(char *s, char *t)
  242. {
  243.     struct name_node *np;
  244.     struct imm_node *ip;
  245.  
  246.     /* name already on name list */
  247.     if (np = nlist_contains(s)) {
  248.         /* arc tail node installed && arc reference realloc'd */
  249.         if ((ip = node_to_arc(np, (struct imm_node *) 0)) != 0
  250.             && (np->imm_ref = realloc(np->imm_ref, strlen(t) + 1)) != NULL) {
  251.             /* update arc reference */
  252.  
  253.             strcpy(np->imm_ref, t);
  254.             return ip;
  255.         }
  256.         return (struct imm_node *) 0;
  257.     }
  258.     /* add name to name list and install arc tail node */
  259.     return node_to_arc(name_to_nlist(s, t), (struct imm_node *) 0);
  260. }
  261.  
  262.  
  263. char *nil = "    ";        /* should be "", but 386BSD 0.1 bus errors XXX */
  264.  
  265. /* Given a name (s), if it is not already on the name list, create a node
  266.  * for it there.  Otherwise, retrieve the name list node.  Create an arc
  267.  * head (i.e., imm_list) node and link it to the tail of the current
  268.  * immediate list.  Return a pointer to the arc head node.  */
  269. struct imm_node *
  270.  link_arc_node(char *s, struct imm_node *tail)
  271. {
  272.     register struct name_node *p;
  273.     register struct imm_node *ip = 0;
  274.  
  275.     /* (name already on name list or added name) and installed new arc
  276.      * and name != arc tail's name */
  277.     if (((p = nlist_contains(s)) != 0 || (p = name_to_nlist(s, nil)) != 0)
  278.         && (ip = node_to_arc(p, tail)) != 0 && strcmp(s, tail_name))
  279.         p->is_arc_